Nhà thờ ban đầu được xây dựng trong một thành lũy (gród) của Poznań, khoảng nửa sau thế kỷ 10 mà ngày nay chính là đảo Ostrów Tumski. Đây là một trong những trung tâm chính trị của nhà nước Ba Lan sơ khai. Các nhà khảo cổ học còn khai quật được cả một cung điện bên dưới nhà thờ Đức mẹ Đồng trinh ở phía trước nhà thờ chính tòa Poznań vào năm 1999. Bên trong cung điện còn có một nhà nguyện, có thể là được xây cho vương hậu Doubravka xứ Bohemia, vợ của vua Mieszko I của Ba Lan. Được biết, vương hậu Doubravka là một người sùng đạo và chính vua Mieszko I cũng làm lễ rửa tội vào năm 966 tại Poznań. Đây là một sự kiện quan trọng trong quá trình Cơ Đốc giáo hoá Ba Lan và củng cố nhà nước sơ khai của Ba Lan. Cũng trong khoảng thời gian này, nhà thờ Poznań đã được xây lên và được nâng cấp lên thành nhà thờ chính tòa vào năm 968 khi vị giám mục truyền giáo đầu tiên, Giám mục Jordan, đến Ba Lan.

Thánh Phêrô là vị thánh bảo trợ đầu tiên của nhà thờ, vì với vai trò là nhà thờ chính tòa đầu tiên của đất nước, nhà thờ Poznań được quyền có cùng một vị thánh bảo trợ như của vương cung thánh đường Thánh Phêrô ở Thành Vatican. Nhà thờ ban đầu được xây dựng theo phong cách Romanesque và có chiều dài khoảng 48 mét. Dấu tích của nhà thờ đầu tiên này vẫn còn có thể thấy trong các tầng hầm của vương cung thánh đường ngày nay. Nhà thờ đầu tiên mang phong cách Romanesque tồn tại trong khoảng bảy mươi năm, cho đến bị đột kích bởi Công tước Bretislav I xứ Bohemia.

Vào thế kỷ 14 và thế kỷ 15, nhà thờ được xây dựng lại theo kiểu kiến trúc Gothic. Đến năm 1622, nhà thờ phải hứng chịu một trận hỏa hoạn gây thiệt hại nghiêm trọng. Sau đó, nhà thờ được trùng tu lại theo phong cách Baroque. Năm 1772, một lần nữa nhà thờ lại bị thiêu rụi và lần này, nhà thờ được cải tạo lại theo phong cách Tân cổ điển. Năm 1821, Giáo hoàng Piô VII đã thêm một vị thánh bảo trợ cho nhà thờ là Thánh Phaolô. Trận đại hỏa hoạn cuối cùng của nhà thờ xảy ra vào ngày 15 tháng 2 năm 1945, trong cuộc giải phóng thành phố khỏi quân Đức quốc xã. Trong lần hỏa hoạn này, nhà thờ bị thiệt hại nghiêm trọng đến mức các nhà bảo tồn quyết định đưa nhà thờ quay trở lại với phong cách Gothic. Nhà thờ được mở cửa trở lại vào ngày 29 tháng 6 năm 1956. Năm 1962, Giáo hoàng Gioan XXIII đã ban cho nhà thờ danh hiệu Tiểu vương cung thánh đường.